(1) Field of the Invention
The present invention relates to an error correcting and detecting system, using error check and correction (ECC) codes, in which single-bit errors are corrected, double-bit errors are detected, triple-bit block errors are detected, quadruple-bit block errors are detected, and 8-bit burst block errors of within any two blocks are detected.
(2) Description of the Related Art
To ensure data integrity and improve the reliability of memory units, error correcting and detecting systems using ECC codes have recently been developed.
ECC codes originated with the Hamming codes disclosed in R. W. Hamming, "Error Detecting and Error Correcting Codes", Bell System Tech. J., vol. 29, No. 2, pp. 147 to 160, April 1950. Hamming codes were used to correct single-bit errors and detect double-bit errors and, therefore, are also called "SEC-DED" codes.
M. Y. Hsiao provided improved Hamming SEC-DED codes to enhance the decoding speed and improve the detection rate of multiple-bit errors (see: "A Class of Optimal Minimum Odd-weight-Column SEC-DED Codes," IBM J. Res. Develop., vol. 14, pp. 395 to 401, July 1970). These "Hsiao" SEC-DED codes have since come into broad use in general-purpose large-scale computers.
The above-mentioned SEC-DED codes are very helpful in ensuring data integrity of memory units and improving the reliability thereof, since the failure mode of an element of a memory unit, i.e., a memory chip is a single-bit error. It is therefore even more effective to construct memory chips, boards, and modules in one-bit configurations.
The remarkable increase in the integration of memory chips and in the density of memory unit packaging, however, means it is no longer practical to construct memory chips, boards, and modules in one-bit configurations in view of memory unit capability, performance, and packaging. Memory chips, boards, and modules are now constructed in multiple-bit configurations, such as 4-bit or 8-bit configurations. For example, a 64K bit memory chip is constructed as 16K words.times.4 bits or 8K words.times.8 bits.
When a plurality of such memory chips are mounted on a memory board or module, the board or module also take on multiple-bit configurations.
In a memory unit constructed by memory chips, boards, or modules of multiple-bit configurations, however, there is a possibility of block (lump) errors in data due to failure of only one of the constituents. In other words, part or all of the bits of a block may be erroneous. It is important to detect such block errors to ensure the data integrity and reliability of memory units.
Here "block" means the multiple-bit configuration. If "b" is the number of bits forming a block, b=4 or b=8 on the above-mentioned memory units.
In view of the, foregoing, proposals have been made for single-bit error correcting, single "b" bit block error detecting (SEC-SbBED) codes and single-bit error correcting, double-bit error detecting, single "b"bit block error detecting (SEC-DED-SbBED) codes.
SEC-SbBED codes are disclosed in Bossen, Chang and Chen, "Measurement and Generation of Error Correcting Codes for Package Failures," IEEE Trans. Comput., vol. C-27, No. 3, pp. 201 to 204, March 1973. With SEC-SbBED codes, the number of check bits (or redundancy bits) is EQU b+ log.sub.2 (r+1) -1
where
b: the number of bits within one block; PA1 r: the number of blocks within one codeword; and PA1 p : the smallest integer greater than or equal to p. PA1 n: the number of bits per one codeword and PA1 k: the number of data bits per one codeword. Also, if b=4 and r=10, the number of check bits is 4+ log.sub.2 11 -1=7. Thus, a (39, 32) SEC-S4BED code is established.
For example, if b=4 and r=18, then the number of check bits is 4+ log.sub.2 19 -1=8. Thus, a (72, 64) SEC-S4BED code is established. Here, (n, k) is defined by
SEC-DED-SbBED codes are disclosed in S. M. Reddy, "A Class of Linear Codes for Error Control in Byte-per-Card Organized Digital Systems," IEEE Trans. Comput., vol. C-27, No. 5, pp. 455 to 459, May 1978 and Dunning and Varanasi, "Code Construction for Error Control in Byte Organized Memory Systems," IEEE Trans. Comput., vol. C-32, No. 6, pp. 535 to 542, June 1983.
With Reddy codes,
(i) if 2.ltoreq.b.ltoreq.4, b+ log.sub.2 (r+1) -1
check bits are required for the SEC-SbBED codes, and one additional check bit is required for the SEC-DED-SbBED codes, and
(ii) if b.gtoreq.5, b+ log.sub.2 (r+1) -1 check bits are required for the SEC-DED-SbBED codes.
Therefore, according to the Reddy codes, if b=4 and r=18, then a (73, 64) SEC-DED-S4BED code is established. If b=4 and r=10, then a (40, 32) SEC-DED-S4BED code is established.
On the other hand, according to the Dunning and Varanasi codes, b+2 check bits are required for the SEC-SbBED codes. In addition, if b.gtoreq.7, then b+ log.sub.2 (r+b+1)/(b+1) +1 check bits are required for the SEC-DED-SbBED codes. If b&lt;7, a larger number of check bits are required for a double-bit error detection (DED) as compared with the Reddy codes.
Unexamined Japanese Patent Publication (Kokai) No. 58-78241, published on May 11, 1983, discloses a (72, 64) SEC-DED-S4BED code.
None of the above-mentioned prior art publications, however, disclose the detection of an 8-bit burst error within any two blocks of a codeword.